/**
 * <p>给你一个字符串 <code>s</code>，找到 <code>s</code> 中最长的回文子串。</p>
 *
 * <p>&nbsp;</p>
 *
 * <p><strong>示例 1：</strong></p>
 *
 * <pre>
 * <strong>输入：</strong>s = "babad"
 * <strong>输出：</strong>"bab"
 * <strong>解释：</strong>"aba" 同样是符合题意的答案。
 * </pre>
 *
 * <p><strong>示例 2：</strong></p>
 *
 * <pre>
 * <strong>输入：</strong>s = "cbbd"
 * <strong>输出：</strong>"bb"
 * </pre>
 *
 * <p>&nbsp;</p>
 *
 * <p><strong>提示：</strong></p>
 *
 * <ul>
 * <li><code>1 &lt;= s.length &lt;= 1000</code></li>
 * <li><code>s</code> 仅由数字和英文字母组成</li>
 * </ul>
 *
 * <div><div>Related Topics</div><div><li>字符串</li><li>动态规划</li></div></div><br><div><li>👍 5575</li><li>👎 0</li></div>
 */

package src.medium._0005.pck;

public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring().new Solution();
        String inputStr = "babad";
        String palindrome = solution.longestPalindrome(inputStr);
        System.out.println("palindrome = " + palindrome);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    @SuppressWarnings("AliControlFlowStatementWithoutBraces")
    class Solution {
        public String longestPalindrome(String s) {
            String ans = "";
            //特殊值处理
            if (s == null) return ans;
            int len = s.length();

            for (int i = 0; i < len; i++) {
                ans = getLongestString(s, ans, len, i - 1, i + 1);
                ans = getLongestString(s, ans, len, i, i + 1);
            }
            return ans;
        }

        private String getLongestString(String s, String ans, int len, int l, int r) {
            while (l >= 0 && r < len && s.charAt(l) == s.charAt(r)) {
                l--;
                r++;
            }
            // 注意：退出条件，可以理解为多移动了一位！！！
            if (ans.length() < r - l - 1) ans = s.substring(l + 1, r);
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
